Distance domination and amplifier placement problems

Title: Distance domination and amplifier placement problems
Creator: Taylor, S.; Wanless, I. M.; Boland, Natashia
Relation: Australasian Journal of Combinatorics Vol. 34, p. 117-136
Relation: http://ajc.maths.uq.edu.au/?page=get_volumes&volume=34
Publisher: Centre for Discrete Mathematics & Computing
Resource Type: journal article
Date: 2006
Description: We consider the optimization problem defined on a connected undirected graph with given root vertex and a parameter s̅, in which we seek a spanning tree with the smallest number of special (amplifying) vertices such that each vertex in the tree is preceded on its unique path from the root vertex by an amplifying vertex no more than s̅ edges distant. This problem, which we called the amplified spanning tree (AST) problem, is motivated by a practical problem in local access television cable networks. We show that even restricted to planar graphs with no vertex degree exceeding four, AST is NP-complete for every fixed s̅ ≥ 1. Making use of a connection with distance domination problems, we show that two related problems, including total distance domination, are also NP-complete and we derive an approximately upper bound for AST.
Subject: amplified spanning tree ( ASP); television; cable networks; vertices
Identifier: http://hdl.handle.net/1959.13/939437
Identifier: uon:12807
Identifier: ISSN:1034-4942
Language: eng
Full Text
Reviewed

		Thumbnail	File	Description	Size	Format
View Details Download			ATTACHMENT01	Publisher version (open access)	270 KB	Adobe Acrobat PDF	View Details Download